package com.zj.leetcode.medium.greed;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @program: algorithm
 * @description: 颜色分类
 * 75 sort-colors
 * @author: Zhang Bo
 * @create: 2022-03-31 12:20:52
 **/
public class SortColors {
    public static void main(String[] args) {
        Solution solution = new SortColors().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void sortColors(int[] nums) {
            if (nums.length <= 1) {
                return;
            }

            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            }
            int i = 0;
            int cur = 0;
            ArrayList<Integer> list = new ArrayList<>();
            while (cur <= 2) {
                Integer value = map.getOrDefault(cur, 0);
                if (value == 0) {
                    cur++;
                } else {
                    nums[i++] = cur;
                    map.put(cur, value - 1);
                }
            }

        }

        /**
         * 双指针 单指针都能做
         * @param nums
         */
        public void sortColors01(int[] nums) {

            int i = 0;
            int len = nums.length - 1;

            while (i < len) {
                if (nums[i] != 0) {
                    int temp = nums[i];
                    nums[i] = nums[i + 1];
                    nums[i + 1] = temp;
                } else if (nums[i] == 1 && nums[i + 1] > 1) {
                    int temp = nums[i];
                    nums[i] = nums[i + 1];
                    nums[i + 1] = temp;
                }

                i++;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
